In unicast routing or packet forwarding, traffic is routed through a network along a single path from the source to the destination host. At each hop along the path, a layer 3 packet forwarding device, such as a router, scans through its routing table for the destination address included in the packet and forwards a single copy of the packet to an outgoing interface (e.g., port) in the direction of the destination host. A layer 2 packet forwarding device also performs a unicast packet forwarding function when it forwards a layer 2 packet to a single destination in response to a match in a layer 2 forwarding table lookup where the matching entry corresponds to a single unicast destination.
In contrast, multicast routing or packet forwarding allows a source host to send packets to a group of destination hosts without requiring that the source hosts copy the packet and send each copy individually to each destination. In layer 3 devices, multicast routing is accomplished by reserving a subset of the IP address space for multicast addresses which are not associated with individual hosts. Instead, multicast packets received by forwarding devices (e.g., routers) are examined and, if the downstream path to members of the multicast group diverge, the router replicates the packet and forwards each copy to the downstream paths. Importantly, the replication of multicast packets is targeted only to those hosts that are members of the multicast group. This contrasts with broadcast delivery of packets which simply replicates and forwards a received packet to all outgoing ports. Thus, layer 3 IP multicast implementations provide for the delivery of source traffic to multiple recipients by replicating multicast packets in the network at the point where paths diverge. Multicast routing therefore results in more efficient delivery of data to multiple recipients compared to other methods (i.e., unicast, broadcast) because packets are delivered only to intended destination hosts without burdening the source host with replicating the packet for delivery each destination host. In layer 2 devices, multicast packet forwarding is accomplished via Internet group management protocol (IGMP) snooping, which will be described in more detail below.
A multicast group is an arbitrary group of hosts (i.e., destinations) wishing to receive a particular packet data stream. A multicast group is a logical grouping that has no physical or geographical boundaries. A host wishing to receive data flowing to a particular group may join a multicast group using a multicast protocol, such as IGMP. As mentioned above, IP multicast addresses specify a set of IP hosts that have joined a group and are interested in receiving multicast traffic designated for that particular group. According to RFC 3171, which is incorporated by reference herein in its entirety, addresses 224.0.0.0 through 239.255.255.255 are designated as multicast addresses. Therefore, if a host wishes to become a member of a multicast group, the sender sends a single datagram to a valid multicast address and intermediary routers copy the packet and send the copies to members of the multicast group.
In order to perform multicast forwarding, conventional layer 3 forwarding devices typically include a forwarding database (FDB) and a port list data structure whose entries are associated in a 1:1 correspondence. For example, each FDB entry typically contains the source IP address of the sender and the group IP addresses for each learned multicast group. FDB entries may also include VLAN identifiers for specifying a VLAN, may only include the group identifier, or may include combinations of the above information. The port list data structure typically includes a plurality of port lists that include a list of outgoing port identifiers indicating the ports to which a received multicast packet should be forwarded. Port lists may also include VLAN identifiers in addition to port identifiers.
Conventional layer 3 multicast forwarding devices typically implement the FDB and the port list data structure using independent hardware structures/resources. For example, the port list data structure may be stored in a first memory and the FDB may be stored in a second memory, with entries in the FDB memory having pointers to memory locations in the port list memory.
One problem associated with conventional IP multicast forwarding devices is that the capacity of the port list data structure can become a resource bottleneck under some conditions. For example, the port list data structure may be limited in the number of port lists, the number of ports per list, and/or the total number of ports across all lists supported. Thus, in networks where a large number of hosts send multicast traffic to the same multicast destinations, port lists stored in the port list data structure may include redundant information. As a result, port list hardware resources may become full and subsequent FDB entries cannot be added. When FDB entries can no longer be added because no port list resources are available, CPU slowpath processing may be used. However, because it is desirable for layer 3 forwarding devices to perform multicast forwarding quickly, it is desirable to limit the amount of slowpath processing performed.
Accordingly, a need exists for improved methods and systems for conserving multicast port list resources in layer 3 forwarding devices.